#ifndef __AUTO_GROWTH_ARRAY_BUFFER_H__
#define __AUTO_GROWTH_ARRAY_BUFFER_H__

#include <stdexcept>
#include <vector>
#include "array_buffer.h"

template<class T, size_t BufferSize = 1024>
class AutoGrowthArrayBuffer
{
public:
	typedef ArrayBuffer<T, BufferSize> buffer_t;
	typedef std::vector<buffer_t*> list_t;

private:
	list_t _list;

public:
	AutoGrowthArrayBuffer() { _list.push_back(new buffer_t); }
	~AutoGrowthArrayBuffer() {
		clear();
		delete _list.back();
	}
	const T& operator[](size_t idx) const {
		ASSERT(idx >= 0 && idx < size() && "Access out of range");
		return get(idx);
	}

	T& operator[](size_t idx) {
		ASSERT(idx >= 0 && idx < size() && "Access out of range");
		return get(idx);
	}

	const T& at(size_t idx) const {
		if (idx < 0 || idx > size()) {
			throw std::out_of_range("invalid CyclicBuffer at()");
		}
		return get(idx);
	}

	T& at(size_t idx) {
		if (idx < 0 || idx > size()) {
			throw std::out_of_range("invalid CyclicBuffer at()");
		}
		return get(idx);
	}

	T& get(size_t idx) {
		return (*_list[idx / BufferSize])[idx % BufferSize];
	}
	size_t bufferSize() const {
		return _list.size();
	}
	buffer_t* getBuffer(size_t idx) const {
		return _list[idx];
	}
	size_t size() const {
		if (_list.size() > 0) {
			return (_list.size() - 1) * BufferSize + _list.back()->size();
		} else {
			return 0;
		}
	}
	template <typename L>
	void sort(L compareFunc) {
		if (size() > 1) {
			internalSort(compareFunc, 0, size() - 1);
		}
	}
	template <typename L>
	void internalSort(L compareFunc, int lo, int hi) {
		//  lo is the lower index, hi is the upper index
		//  of the region of array a that is to be sorted
		int i=lo, j=hi;
		T x=(*this)[(lo+hi)/2];

		//  partition
		do
		{    
			while (compareFunc((*this)[i],x)) 
				i++; 
			while (compareFunc(x,(*this)[j])) 
				j--;
			if (i<=j)
			{
				swap(i,j);
				i++; j--;
			}
		} while (i<=j);

		//  recursion
		if (lo<j) 
			internalSort( compareFunc, lo, j);
		if (i<hi) 
			internalSort( compareFunc, i, hi);
	}
	void swap(int i, int j) {
		T temp = get(j);
		get(j) = get(i);
		get(i) = temp;
	}
	int capacity() const { return _list.size() * BufferSize; }
	bool empty() const { return _list.empty() || _list.back()->empty(); }
	bool full() const { return size() >= capacity(); }
	void clear() { 
		while (_list.size() > 1) {
			delete _list.back();
			_list.pop_back();
		}
		_list.back()->clear();
	}

	T& front() {
		ASSERT(!empty() && "Access empty");
		return _list.front()->front();
	}

	const T& front() const{
		ASSERT(!empty() && "Access empty");
		return _list.front()->front();
	}

	T& back() {
		ASSERT(!empty() && "Access empty");
		return _list.back()->back();
	}

	const T& back() const {
		ASSERT(!empty() && "Access empty");
		return _list.back()->back();
	}

	void push_back(const T& value) {
		if (_list.empty() || _list.back()->full()) {
			_list.push_back(new buffer_t);
		}
		_list.back()->push_back(value);
	}
	void pop_back() {
		ASSERT(!empty() && "Pop empty");
		_list.back()->pop_back();
	}
	template<class internal_T, size_t internal_BufferSize>
	class _AutoGrowthArrayBuffer_const_iterator
	{
	protected:
		typedef _AutoGrowthArrayBuffer_const_iterator<internal_T, internal_BufferSize> _my_t;
		typedef AutoGrowthArrayBuffer<internal_T, internal_BufferSize> _container_t;
		typedef ArrayBuffer<internal_T, internal_BufferSize> _buffer_t;
		typedef std::vector<_buffer_t*> _list_t;

		_list_t* _internalList;
		int _currentListIndex;
		int _currentBufferIndex;

		_container_t* _container;
	public:
		_AutoGrowthArrayBuffer_const_iterator() { }

		_AutoGrowthArrayBuffer_const_iterator(_list_t* list, int listIndex, int bufferIndex, _container_t* containerPtr) {
			_internalList = list;
			_currentListIndex = listIndex;
			_currentBufferIndex = bufferIndex;
			_container = containerPtr;
		}

		_AutoGrowthArrayBuffer_const_iterator(_list_t* list, int listIndex, int bufferIndex) {
			_internalList = list;
			_currentListIndex = listIndex;
			_currentBufferIndex = bufferIndex;
			_container = 0;
		}
		const internal_T* operator->() const {
			return (&**this);
		}

		// follow 4 function is important.
		const internal_T& operator*() const {
			_buffer_t& buffer = *((*_internalList)[_currentListIndex]);
			return buffer[_currentBufferIndex];
		}

		_my_t& operator++() {
			_buffer_t* buffer = (*_internalList)[_currentListIndex];
			if (_currentBufferIndex >= static_cast<int>(buffer->size()) - 1
					&& _currentListIndex < static_cast<int>(_internalList->size()) - 1) {
				++_currentListIndex;
				_currentBufferIndex = 0;
			} else {
				++_currentBufferIndex;
			}
			return (*this);
		}
		_my_t& operator--() {
			if (_currentBufferIndex <= 0 && _currentListIndex > 0) {
				--_currentListIndex;
				_currentBufferIndex = internal_BufferSize;
			} else {
				--_currentBufferIndex;
			}
			return (*this);
		}

		bool operator==(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			return (_currentListIndex == right._currentListIndex) && (_currentBufferIndex == right._currentBufferIndex);
		}

		bool operator!=(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			return (!(*this == right));
		}

		_my_t operator++(int) {
			_my_t result = *this;
			++*this;
			return (result);
		}

		_my_t operator--(int) {
			_my_t result = *this;
			--*this;
			return (result);
		}
#ifdef COMPLEX_ITERATOR

		_my_t operator+(ptrdiff_t off) const {
			_my_t result = *this;
			return (result += off);
		}

		_my_t& operator-=(ptrdiff_t off) {
			return (*this += -off);
		}

		_my_t operator-(ptrdiff_t off) const
		{	// return this - integer
			_my_t result = *this;
			return (result -= off);
		}

		internal_T& operator[](ptrdiff_t off) const {
			return (*(*this + off));
		}

		bool operator<(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			if (_list_it < right._list_it) {
				return true;
			} else if (_list_it == right._list_it) {
				return _buffer_it < right._buffer_it;
			} else {
				return false;
			}
		}

		bool operator>(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			return (right < *this);
		}

		bool operator<=(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			return (!(right < *this));
		}

		bool operator>=(const _my_t& right) const {
			ASSERT(_container == right._container && "not same container");
			return (!(*this < right));
		}
	};

	template<class internal_T>
	inline _AutoGrowthArrayBuffer_const_iterator<internal_T> operator+(ptrdiff_t off, _AutoGrowthArrayBuffer_const_iterator<internal_T> next) {
		return (next += off);
	}
#else //COMPLEX_ITERATOR
	};
#endif //COMPLEX_ITERATOR

	template<class internal_T, size_t internal_BufferSize>
	class _AutoGrowthArrayBuffer_iterator : public _AutoGrowthArrayBuffer_const_iterator<internal_T, internal_BufferSize>
	{
		typedef _AutoGrowthArrayBuffer_iterator<internal_T, internal_BufferSize> _my_t;
		typedef AutoGrowthArrayBuffer<internal_T, internal_BufferSize> _container_t;
		typedef _AutoGrowthArrayBuffer_const_iterator<internal_T, internal_BufferSize> _my_base_t;
		typedef ArrayBuffer<internal_T, internal_BufferSize> _buffer_t;
		typedef std::vector<_buffer_t*> _list_t;
	public:
		_AutoGrowthArrayBuffer_iterator() { }

		_AutoGrowthArrayBuffer_iterator(_list_t* list, int listIndex, int bufferIndex, _container_t* containerPtr)
			: _my_base_t(list, listIndex, bufferIndex) { }

		_AutoGrowthArrayBuffer_iterator(_list_t* list, int listIndex, int bufferIndex)
			: _my_base_t(list, listIndex, bufferIndex) { }

		internal_T& operator*() const {
			return ((internal_T&)**(_my_base_t *)this);
		}

		internal_T* operator->() const {
			return (&**this);
		}

		_my_t& operator++() {
			++(*(_my_base_t *)this);
			return (*this);
		}

		_my_t operator++(int) {
			_my_t result = *this;
			++*this;
			return (result);
		}

		_my_t& operator--() {
			--(*(_my_base_t *)this);
			return (*this);
		}

		_my_t operator--(int) {
			_my_t result = *this;
			--*this;
			return (result);
		}

#ifdef COMPLEX_ITERATOR

		_my_t operator+(ptrdiff_t off) const {
			_my_t result = *this;
			return (result += off);
		}

		_my_t& operator-=(ptrdiff_t off) {
			return (*this += -off);
		}

		_my_t operator-(ptrdiff_t off) const {
			_my_t result = *this;
			return (result -= off);
		}

		ptrdiff_t operator-(const _my_base_t& right) const
		{	// return difference of iterators
			return (*(_my_base_t *)this - right);
		}

		internal_T& operator[](ptrdiff_t off) const {
			return (*(*this + off));
		}
	};
#else //COMPLEX_ITERATOR
	};
#endif //COMPLEX_ITERATOR

	typedef _AutoGrowthArrayBuffer_const_iterator<T, BufferSize> const_iterator;
	typedef _AutoGrowthArrayBuffer_iterator<T, BufferSize> iterator;

	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

#ifdef _DEBUG
	iterator begin() {
		return (iterator(&_list, 0, 0, this));
	}

	const_iterator begin() const
	{	// return iterator for beginning of nonmutable sequence
		return (const_iterator(&_list, 0, 0, this));
	}

	iterator end()
	{	// return iterator for end of mutable sequence
		return (iterator(&_list, _list.size() - 1, _list.back()->size(), this));
	}

	const_iterator end() const
	{	// return iterator for end of nonmutable sequence
		return (const_iterator(&_list, _list.size() - 1, _list.back()->size(), this));
	}
#else /* _DEBUG */
	iterator begin()
	{	// return iterator for beginning of mutable sequence
		return (iterator(&_list, 0, 0));
	}

	const_iterator begin() const
	{	// return iterator for beginning of nonmutable sequence
		return (const_iterator(&_list, 0, 0));
	}

	iterator end()
	{	// return iterator for end of mutable sequence
		return (iterator(&_list, _list.size() - 1, _list.back()->size()));
	}

	const_iterator end() const
	{	// return iterator for end of nonmutable sequence
		return (const_iterator(&_list, _list.size() - 1, _list.back()->size()));
	}
#endif /* _DEBUG */
	reverse_iterator rbegin() {
		return (reverse_iterator(end()));
	}

	const_reverse_iterator rbegin() const {
		return (const_reverse_iterator(end()));
	}

	reverse_iterator rend() {
		return (reverse_iterator(begin()));
	}

	const_reverse_iterator rend() const {
		return (const_reverse_iterator(begin()));
	}

	iterator erase(iterator where) {
		*where = back();
		pop_back();
		return iterator(where);
	}
};

#endif //__AUTO_GROWTH_ARRAY_BUFFER_H__